import collections
import heapq
class Solution(object):
    def rearrangeString(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        if k == 0:
            return s
        d = collections.Counter(s)
        l = []
        for key in d:
            l.append((- d[key], key))
        heapq.heapify(l)
        node_max = - l[0][0]
        s_list = ['' for _ in range(node_max)]
        index = 0
        while l:
            node = heapq.heappop(l)
            value = node[1]
            count = - node[0]
            j = 0
            if count == node_max:
                while j < count:
                    s_list[index % node_max] += value
                    j += 1
                    index += 1
            else:
                while j < count:
                    if index % node_max == node_max - 1:
                        index += 1
                    s_list[index % node_max] += value
                    j += 1
                    index += 1
        for item in s_list[:-1]:
            if len(item) < k:
                return ''
        return ''.join(s_list)


data = Solution()
s = "aaabc"
k = 3
print(data.rearrangeString(s, k))
s = "aabbcc"
k = 3
print(data.rearrangeString(s, k))
s = "aaadbbcc"
k = 3
print(data.rearrangeString(s, k))
s = "abb"
k = 2
print(data.rearrangeString(s, k))
s = "a"
k = 0
print(data.rearrangeString(s, k))
s = "aabbcc"
k = 4
print(data.rearrangeString(s, k))
s = "abeabac"
k = 3
print(data.rearrangeString(s, k))